package com.shm.leetcode;

/**
 * 85. 最大矩形
 * 给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
 * 输出：6
 * 解释：最大矩形如上图所示。
 * 示例 2：
 *
 * 输入：matrix = []
 * 输出：0
 * 示例 3：
 *
 * 输入：matrix = [["0"]]
 * 输出：0
 * 示例 4：
 *
 * 输入：matrix = [["1"]]
 * 输出：1
 * 示例 5：
 *
 * 输入：matrix = [["0","0"]]
 * 输出：0
 *
 *
 * 提示：
 *
 * rows == matrix.length
 * cols == matrix[0].length
 * 0 <= row, cols <= 200
 * matrix[i][j] 为 '0' 或 '1'
 * @author SHM
 */
public class MaximalRectangle {
    /**
     * 方法一: 使用柱状图的优化暴力方法
     * 思路与算法
     *
     * 最原始地，我们可以列举每个可能的矩形。我们枚举矩形所有可能的左上角坐标和右下角坐标，并检查该矩形是否符合要求。然而该方法的时间复杂度过高，不能通过所有的测试用例，因此我们必须寻找其他方法。
     *
     * 我们首先计算出矩阵的每个元素的左边连续 11 的数量，使用二维数组 \textit{left}left 记录，其中 \textit{left}[i][j]left[i][j] 为矩阵第 ii 行第 jj 列元素的左边连续 11 的数量。
     *
     *
     * 10 / 10
     *
     * 随后，对于矩阵中任意一个点，我们枚举以该点为右下角的全 11 矩形。
     *
     * 具体而言，当考察以 \textit{matrix}[i][j]matrix[i][j] 为右下角的矩形时，我们枚举满足 0 \le k \le i0≤k≤i 的所有可能的 kk，此时矩阵的最大宽度就为
     *
     * \textit{left}[i][j], \textit{left}[i-1][j], \ldots, \textit{left}[k][j]
     * left[i][j],left[i−1][j],…,left[k][j]
     *
     * 的最小值。
     *
     * 下图有助于理解。给定每个点的最大宽度，可计算出底端黄色方块的最大矩形面积。
     *
     *
     * 1 / 7
     *
     * 对每个点重复这一过程，就可以得到全局的最大矩形。
     *
     * 我们预计算最大宽度的方法事实上将输入转化成了一系列的柱状图，我们针对每个柱状图计算最大面积。
     *
     *
     *
     * 于是，上述方法本质上是「84. 柱状图中最大的矩形」题中优化暴力算法的复用。
     * 复杂度分析
     *
     * 时间复杂度：O(m^2n)O(m
     * 2
     *  n)，其中 mm 和 nn 分别是矩阵的行数和列数。计算 \textit{left}left 矩阵需要 O(mn)O(mn) 的时间。随后对于矩阵的每个点，需要 O(m)O(m) 的时间枚举高度。故总的时间复杂度为 O(mn) + O(mn) \cdot O(m) = O(m^2n)O(mn)+O(mn)⋅O(m)=O(m
     * 2
     *  n)。
     *
     * 空间复杂度：O(mn)O(mn)，其中 mm 和 nn 分别是矩阵的行数和列数。我们分配了一个与给定矩阵等大的数组，用于存储每个元素的左边连续 11 的数量。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/maximal-rectangle/solution/zui-da-ju-xing-by-leetcode-solution-bjlu/
     * @param matrix
     * @return
     */
    public int maximalRectangle(char[][] matrix) {
        int n = matrix.length;
        if(n==0){
            return 0;
        }
        int m = matrix[0].length;
        int[][] left = new int[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(matrix[i][j]=='1'){
                    left[i][j]=(j==0?0:left[i][j-1])+1;
                }
            }
        }

        int ret = 0;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(matrix[i][j]=='0'){
                    continue;
                }
                int width = left[i][j];
                int  area = width;
                for(int k=i-1;k>=0;k--){
                    width = Math.min(width,left[k][j]);
                    area = Math.max(area,(i-k+1)*width);
                }
                ret = Math.max(ret,area);
            }
        }
        return ret;
    }
}
